package main

import ()

func isMatch(s string, p string) bool {
	if len(p)==0{
		if len(s)==0{
			return true
		}else{
			return false
		}
	}


	if len(s)==0 && len(p)==1{
		return false
	}

	m := len(s)+1
	n := len(p)+1

	dp := make([][]bool,m)
	for i:=0;i<m;i++{
		dp[i] = make([]bool,n)
	}

	dp[0][0] = true

	// 初始化第一行
	for j:=2;j<n;j++{
		if p[j-1]=='*'{
			dp[0][j] = dp[0][j-2]
		}
	}

	for r:=1;r<m;r++{
		i := r-1
		for c:=1;c<n;c++{
			j := c-1
			if s[i]==p[j] || p[j]=='.'{
				dp[r][c] = dp[r-1][c-1]
			}else if p[j]=='*'{
				if p[j-1]==s[i] || p[j-1]=='.'{
					dp[r][c] = dp[r-1][c] || dp[r][c-2]
				}else{
					dp[r][c] = dp[r][c-2]
				}
			}else{
				dp[r][c] = false
			}
		}
	}
	return dp[m-1][n-1]
}

func main() {
	
}
